package problem433;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

//433.最小基因变化
//https://leetcode.cn/problems/minimum-genetic-mutation/

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> vis = new HashSet<>();
        Set<String> hash = new HashSet<>();
        for(String s : bank) hash.add(s);
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        vis.add(startGene);
        int step = 0;
        char[] change = {'A', 'C', 'G', 'T'};
        if(!hash.contains(endGene)) return -1;
        while(!queue.isEmpty()) {
            int size = queue.size();
            step++;
            while(size -- > 0) {
                String str = queue.poll();
                for(int i = 0; i<8; i++) {
                    char[] t = str.toCharArray();
                    for(int j = 0; j<4; j++) {
                        t[i] = change[j];
                        String next = new String(t);
                        if(next.equals(endGene)) return step;
                        if(!vis.contains(next) && hash.contains(next)) {
                            queue.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}